using System;
using Collections = System.Collections.Generic;
using Diagnostics = System.Diagnostics;
using Microsoft.Scripting.Internal.Ast;
using Microsoft.Scripting;
using Microsoft.Scripting.Hosting;
using Nua.Ast;

namespace Nua.Compiler
{
	// Interprets a sequence of tokens to build an abstract syntax tree for a
	// Lua program
	public class Parser
	{
		internal readonly Statement Result;

		private ErrorSink errors;
        private ParserSink sink;
		private readonly Scanner tokens;

        private SourceUnit sourceUnit;
        private CodeBlock topLevel;
 
        private Collections.Stack<FunctionDecl> _functions;
        private SourceUnitReader _sourceReader;
        public Collections.List<NamedVar> variables = new Collections.List<NamedVar>();

		internal Parser(Scanner tokens, CodeBlock block, ErrorSink errors)
		{
			this.tokens = tokens;
			this.errors = errors;
            this.topLevel = block;
            this.sourceUnit = tokens.SourceUnit;
			this.Result = this.ParseChunk(TokenKind.EndOfFile);
 
			if (this.tokens.Peek().Kind != TokenKind.EndOfFile)
			{
				errors.Add(sourceUnit, "expected end-of-file", tokens.Peek().Span, 0, Severity.FatalError);
			}   

            block.Body = this.Result;
		}

        public ErrorSink ErrorSink {
            get {
                return errors;
            }
            set {
                if (value == null) throw new ArgumentNullException("value");
                errors = value; 
            }
        }

        public ParserSink ParserSink {
            get {
                return sink;
            }
            set {
                if (value == null) throw new ArgumentNullException("value");
                sink = value;
            }
        }


		// Skips tokens up to one of the specified tokens; this is to
		// resynchronise the parser and hopefully avoid cascading streams
		// of error messages
		private void Resync(TokenKind token)
		{
			while (this.tokens.Peek().Kind != TokenKind.EndOfFile &&
				   (this.tokens.Peek().Kind & token) == 0)
			{
				this.tokens.Read();
			}
		}

		// Resyncs, and produces an error, unless we already synced to EOF.
		// This stops cascading 'expected blah' error messages.
		private void ResyncWithError(TokenKind token, string error)
		{
			this.Resync(token);
			if (this.tokens.Peek().Kind != TokenKind.EndOfFile || this.errors.ErrorCount == 0)
			{
				this.errors.Add(sourceUnit, error, GetSpan(), 0, Severity.FatalError);
			}
		}

		// Parses a chunk-- a sequence of statements, optionally separated by
		// semicolons
		private Statement ParseChunk(TokenKind follow)
		{
			Statement result = new EmptyStmt();

            while ((this.tokens.Peek().Kind & (follow | TokenKind.EndOfFile)) == 0)
			{
				Statement stmt = this.ParseStmt(TokenKind.Semi | follow);

				if (stmt != null)
				{
					result = new CompoundStmt(stmt.Span, result, stmt);
				}

				if (this.tokens.Peek().Kind == TokenKind.Semi)
				{
					this.tokens.Read();
				}

				// This parser can handle break statements in the middle of a
				// block, but for compatibility with Lua we check this
				// restriction
				if ((stmt is BreakStmt || stmt is ReturnStmt) && (this.tokens.Peek().Kind & follow) == 0)
				{
					this.errors.Add(sourceUnit, "break or return statements must be the last statement in a block", GetSpan(), 0, Severity.FatalError);
				}
			}

			return result;
		}

        private SourceSpan GetSpan()
        {
            return this.tokens.Peek().Span;
        }

		// Parses a statement
		private Statement ParseStmt(TokenKind follow)
		{
			switch (this.tokens.Peek().Kind)
			{
				case TokenKind.Do:
					this.tokens.Read();
					Statement result = this.ParseChunk(TokenKind.End);

					if (this.tokens.Peek().Kind == TokenKind.End)
					{
						this.tokens.Read();
						return result;
					}
					else
					{
						this.ResyncWithError(follow, "expected 'end'");
						return null;
					}

				case TokenKind.While:
                    this.tokens.Read();
					Expression condition = this.ParseExpr(TokenKind.Do);

					if (this.tokens.Peek().Kind != TokenKind.Do)
					{
						this.ResyncWithError(follow, "expected 'do'");
						return null;
					}

					this.tokens.Read();
					Statement body = this.ParseChunk(TokenKind.End);

					if (this.tokens.Peek().Kind == TokenKind.End)
					{
						this.tokens.Read();
						return new WhileStmt(GetSpan(), condition, body);
					}
					else
					{
						this.ResyncWithError(follow, "expected 'end'");
						return null;
					}

				case TokenKind.Repeat:
                    this.tokens.Read();
					body = this.ParseChunk(TokenKind.Until);

					if (this.tokens.Peek().Kind != TokenKind.Until)
					{
						this.ResyncWithError(follow, "expected 'until'");
						return null;
					}

					this.tokens.Read();
					condition = this.ParseExpr(follow);
					return new RepeatStmt(GetSpan(), body, condition, SourceLocation.None);

				case TokenKind.If:
                    this.tokens.Read();
					condition = this.ParseExpr(TokenKind.Then);

					if (this.tokens.Peek().Kind != TokenKind.Then)
					{
						this.ResyncWithError(follow, "expected 'then'");
						return null;
					}

					this.tokens.Read();
					body = this.ParseChunk(TokenKind.Else | TokenKind.ElseIf | TokenKind.End);

					IfStmt accum = new IfStmt(GetSpan(), condition, body, new EmptyStmt());
					result = accum;

					while (this.tokens.Peek().Kind == TokenKind.ElseIf)
					{
                        this.tokens.Read();
						condition = this.ParseExpr(TokenKind.Then);

						if (this.tokens.Peek().Kind != TokenKind.Then)
						{
							this.ResyncWithError(follow, "expected 'then'");
							return null;
						}

						this.tokens.Read();
						body = this.ParseChunk(TokenKind.ElseIf | TokenKind.Else | TokenKind.End);
						IfStmt falseBranch = new IfStmt(GetSpan(), condition, body, accum.FalseBranch);
						accum.FalseBranch = falseBranch;
						accum = falseBranch;
					}

					if (this.tokens.Peek().Kind == TokenKind.Else)
					{
						this.tokens.Read();
                        accum = new IfStmt(GetSpan(), condition, body, this.ParseChunk(TokenKind.End));
                        result = accum;
					}

					if (this.tokens.Peek().Kind != TokenKind.End)
					{
						this.ResyncWithError(follow, "expected 'end'");
						return null;
					}

					this.tokens.Read();
					return result;

				case TokenKind.Return:
					// Return must be last statement in block, so look ahead
					// for follow set
		            this.tokens.Read();
					if ((this.tokens.Peek().Kind & follow) == 0)
					{
						return new ReturnStmt(GetSpan(), this.ParseExpList(follow));
					}
					else
					{
						return new ReturnStmt(GetSpan(), new Collections.List<Expression>());
					}

				case TokenKind.Break:
                    this.tokens.Read();
					return new BreakStmt(GetSpan());

				case TokenKind.For:
                    this.tokens.Read();
					if (this.tokens.Peek().Kind != TokenKind.Identifier)
					{
						this.ResyncWithError(follow, "expected identifier");
						return null;
					}

					Token token = this.tokens.Read();
					LocalDecl decl = new LocalDecl(GetSpan(), (string)token.Value);

					// Have to distinguish for and foreach
					if (this.tokens.Peek().Kind == TokenKind.Equals)
					{
						// 'for' loop
						this.tokens.Read();

						Expression lowerBound = this.ParseExpr(TokenKind.Comma);

						if (this.tokens.Peek().Kind != TokenKind.Comma)
						{
							this.ResyncWithError(follow, "expected ','");
							return null;
						}

						this.tokens.Read();
						Expression upperBound = this.ParseExpr(TokenKind.Comma | TokenKind.Do);
						Expression step = null;

						if (this.tokens.Peek().Kind == TokenKind.Comma)
						{
							this.tokens.Read();
							step = this.ParseExpr(TokenKind.Do);
						}
						else
						{
							step = new LiteralExpr(GetSpan(), 1.0d);
						}

						if (this.tokens.Peek().Kind != TokenKind.Do)
						{
							this.ResyncWithError(follow, "expected 'do'");
							return null;
						}

						this.tokens.Read();
						body = this.ParseChunk(TokenKind.End);

						if (this.tokens.Peek().Kind != TokenKind.End)
						{
							this.ResyncWithError(follow, "expected 'end'");
							return null;
						}

						this.tokens.Read();
						return new ForStmt(GetSpan(), decl, lowerBound, upperBound, step, body);
					}
					else
					{
						// 'foreach' loop

						Collections.IList<LocalDecl> decls = new Collections.List<LocalDecl>();
						decls.Add(decl);

						// Parse rest of the comma-separated name list, if any

						if (this.tokens.Peek().Kind == TokenKind.Comma)
						{
							this.tokens.Read();
							bool done = false;

							do
							{
								if (this.tokens.Peek().Kind != TokenKind.Identifier)
								{
									this.ResyncWithError(follow, "expected identifier");
									return null;
								}

								token = this.tokens.Read();
								decls.Add(new LocalDecl(GetSpan(), (string)token.Value));

								if (this.tokens.Peek().Kind == TokenKind.Comma)
								{
									this.tokens.Read();
								}
								else
								{
									done = true;
								}
							}
							while (!done);
						}

						if (this.tokens.Peek().Kind != TokenKind.In)
						{
							this.ResyncWithError(follow, "expected 'in'");
							return null;
						}

						this.tokens.Read();
						Collections.IList<Expression> exprs = this.ParseExpList(TokenKind.Do);

						if (this.tokens.Peek().Kind != TokenKind.Do)
						{
							this.ResyncWithError(follow, "expected 'do'");
							return null;
						}

						this.tokens.Read();
						body = this.ParseChunk(TokenKind.End);

						if (this.tokens.Peek().Kind != TokenKind.End)
						{
							this.ResyncWithError(follow, "expected 'end'");
							return null;
						}

						this.tokens.Read();
						return new ForEachStmt(GetSpan(), decls, exprs, body);
					}

				case TokenKind.Function:
					return this.ParseFunDecl(follow, false);

				case TokenKind.Local:
	                this.tokens.Read();
					// Have to distinguish variable and function decl
					if (this.tokens.Peek().Kind == TokenKind.Function)
					{
						// Function decl
						return this.ParseFunDecl(follow, true);
					}
					else
					{
						// Var decl

						Collections.IList<LocalDecl> locals = new Collections.List<LocalDecl>();
						bool done = false;

						do
						{
							if (this.tokens.Peek().Kind != TokenKind.Identifier)
							{
								this.ResyncWithError(follow, "expected identifier");
								return null;
							}

							token = this.tokens.Read();
							locals.Add(new LocalDecl(GetSpan(), (string)token.Value));

							if (this.tokens.Peek().Kind == TokenKind.Comma)
							{
								this.tokens.Read();
							}
							else
							{
								done = true;
							}
						}
						while (!done);

						Collections.IList<Expression> init = null;

						if (this.tokens.Peek().Kind == TokenKind.Equals)
						{
							this.tokens.Read();
							init = this.ParseExpList(follow);
						}

						return new LocalVarDecl(GetSpan(), locals, init);
					}

				default:
					// Assignment or function call
					Expression expr = this.ParseExpr(TokenKind.Equals | TokenKind.Comma | follow);

					if ((this.tokens.Peek().Kind & (TokenKind.Equals | TokenKind.Comma)) == 0)
					{
						// Function call
						return this.ParseFunctionCall(follow, expr);
					}
					else
					{
						// Assignment statement
						return this.ParseAssignment(follow, expr);
					}
			}
		}

		// Parses an assignment statement; assignment statements are complex
		// and can assign in 'parallel' many expressions to many lvalues
		private Statement ParseAssignment(TokenKind follow, Expression firstExpr)
		{
			// Check expression speculatively parsed is lvalued-expression

			Var firstVar = firstExpr as Var;

			if (firstExpr != null && firstVar == null)
			{
				this.errors.Add(sourceUnit, "expected lvalued expression", GetSpan(), 0, Severity.FatalError);
			}

			Collections.IList<Var> vars = new Collections.List<Var>();
			vars.Add(firstVar);

			// Parse comma-separated list of lvalues

			if (this.tokens.Peek().Kind == TokenKind.Comma)
			{
				this.tokens.Read();
				bool done = false;

				do
				{
					vars.Add(this.ParseVar(TokenKind.Comma | TokenKind.Equals));

					if (this.tokens.Peek().Kind == TokenKind.Comma)
					{
						this.tokens.Read();
					}
					else
					{
						done = true;
					}
				}
				while (!done);
			}

			// Must consume an equals now; if not, error
			if (this.tokens.Peek().Kind != TokenKind.Equals)
			{
				this.ResyncWithError(follow, "expected '='");
				return null;
			}

            // read the equals
            this.tokens.Read();

			// Parse comma-separateed list of expressions
			Collections.IList<Expression> exprs = this.ParseExpList(follow);

			return new Assign(GetSpan(), vars, exprs);
		}

		private Collections.IList<Expression> ParseExpList(TokenKind follow)
		{
			Collections.IList<Expression> exprs = new Collections.List<Expression>();
			bool done = false;

			do
			{
				exprs.Add(this.ParseExpr(TokenKind.Comma | follow));

				if (this.tokens.Peek().Kind == TokenKind.Comma)
				{
					this.tokens.Read();
				}
				else
				{
					done = true;
				}
			}
			while (!done);

			return exprs;
		}

		private Statement ParseFunctionCall(TokenKind follow, Expression expr)
		{
			FunctionCall result = expr as FunctionCall;
			if (result == null)
			{
				this.ResyncWithError(follow, "expected function call");
			}
			return new IgnoreStmt(expr == null ? GetSpan() : expr.Span, expr);
		}

		private Statement ParseFunDecl(TokenKind follow, bool local)
		{
			if (this.tokens.Peek().Kind != TokenKind.Function)
			{
				this.ResyncWithError(follow, "expected 'function'");
				return null;
			}

			return new FunctionDecl(GetSpan(), local, this.ParseFunName(TokenKind.LeftRound), this.ParseFuncBody(follow));
		}

		private Var ParseFunName(TokenKind follow)
		{
			Var result = null;

			while ((this.tokens.Peek().Kind == TokenKind.Identifier) || (this.tokens.Peek().Kind == TokenKind.Dot))
			{
				Token t = this.tokens.Read();

				if (t.Kind == TokenKind.Identifier)
                {
					result = new NamedVar(t.Span, (string)t.Value, topLevel);
                    // TODO:// code block is presumably the way they do the relavent scoping
                    bool found = false;
                    foreach (NamedVar n in variables)
                        if (n.Name == ((NamedVar)result).Name)
                            found = true;
                    if (!found)
                        variables.Add((NamedVar)result);
                }

				else if (t.Kind == TokenKind.Dot)
				{
					if (this.tokens.Peek().Kind != TokenKind.Identifier)
					{
						this.ResyncWithError(follow, "expected identifier");
						return null;
					}

					Token tt = this.tokens.Read();
					result = new Slot(t.Span, result, new LiteralExpr(tt.Span, (string)tt.Value));
				}
			}
			return result;
		}

/*
	var, prefixexp and functioncall are left-recursive in the original Lua
	grammar. I recast them here as right-recursive so our recursive-descent
	parser can parse them without infinitely looping

	Original grammar:

	var ::= Name
		  | prefixexp '[' exp ']'
		  | prefixexp '.' Name

	prefixexp ::=
		    var
		  | functioncall
		  | '(' exp ')'

	functioncall ::=
		    prefixexp args
		  | prefixexp ':' Name args

	Right-recursive grammar:

	prefixexp ::=
		    Name suffix_opt
		  | '(' exp ')' suffix

	suffix_opt ::=
		    eps
		  | suffix

	suffix ::=
		    '[' exp ']' suffix_opt
		  | '.' Name suffix_opt
		  | args suffix_opt
		  | ':' Name args suffix_opt

	var and functioncall productions are unchanged, but in practice suffix must
	be non-greedy because a functioncall must have a 'functioncall suffix' and
	a var must have a 'var suffix' (e.g. a function call is not an lvalue, thus
	isn't suitable as a var, but the prefixexp rule will chomp the trailing
	[exp] or .Name *and* admit function calls like :Name(); we need to handle
	this!
 */
		private Var ParseVar(TokenKind follow)
		{
			Expression expr = this.ParsePrefixExpr(follow);
			Var result = expr as Var;
			if (result == null)
			{
				this.ResyncWithError(follow, "expected var");
			}
			return result;
		}

		private Expression ParsePrefixExpr(TokenKind follow)
		{
			const TokenKind SuffixLookAhead =
				TokenKind.LeftSquare | TokenKind.Dot |
				TokenKind.Colon | TokenKind.LeftRound |
				TokenKind.LeftCurly | TokenKind.NumericLiteral |
				TokenKind.StringLiteral | TokenKind.True |
				TokenKind.False | TokenKind.Nil;

//			Diagnostics.Debug.Assert(
//				(follow & SuffixLookAhead) == 0,
//				"expect to be able to peek one token to continue parsing suffixes");

			Expression result;
			Collections.IList<Arg> args;

			switch (this.tokens.Peek().Kind)
			{
				case TokenKind.Identifier:
					Token token = this.tokens.Read();
					
					result = new NamedVar(token.Span, (string)token.Value, topLevel);
                    // TODO:// code block is presumably the way they do the relavent scoping
                    bool found = false;
                    foreach (NamedVar n in variables)
                        if (n.Name == ((NamedVar)result).Name)
                            found = true;
                    if (!found)
                        variables.Add((NamedVar)result);


					if ((this.tokens.Peek().Kind & SuffixLookAhead) == 0)
					{
						// no suffix
						return result;
					}

					break;

				case TokenKind.LeftRound:
                    this.tokens.Read();
					// TODO: is this expression necessarily single-valued?
					result = new SingleValueExpr(GetSpan(), this.ParseExpr(TokenKind.RightRound));

					if (this.tokens.Peek().Kind == TokenKind.RightRound)
					{
						this.tokens.Read();
					}
					else
					{
						this.ResyncWithError(follow, "expected ')'");
						return null;
					}

					break;

				default:
					this.ResyncWithError(follow, "expected identifier or '('");
					return null;
			}

			while ((this.tokens.Peek().Kind & SuffixLookAhead) != 0)
			{
				switch (this.tokens.Peek().Kind)
				{
					case TokenKind.LeftSquare:
                        this.tokens.Read();
						Expression slotExpr = this.ParseExpr(TokenKind.RightSquare);

						if (this.tokens.Peek().Kind == TokenKind.RightSquare)
						{
							this.tokens.Read();
							result = new Slot(GetSpan(), result, slotExpr);
						}
						else
						{
							this.ResyncWithError(follow, "expected ']'");
							return null;
						}

						break;

					case TokenKind.Dot:
	                    this.tokens.Read();
						if (this.tokens.Peek().Kind == TokenKind.Identifier)
						{
							Token token = this.tokens.Read();
							result = new Slot(GetSpan(), result, new LiteralExpr(GetSpan(), token.Value));
						}
						else
						{
							this.ResyncWithError(follow, "expected identifier");
							return null;
						}

						break;

					case TokenKind.Colon:
                        this.tokens.Read();
						if (this.tokens.Peek().Kind == TokenKind.Identifier)
						{
							string name = (string)this.tokens.Read().Value;
							args = this.ParseArgs(follow | SuffixLookAhead);
                            Arg[] tempArray = new Arg[args.Count];
                            for (int i=0;i<args.Count;i++)
                                tempArray[i] = args[i];
							result = new FunctionCall(GetSpan(), result, name, tempArray);
						}
						else
						{
							this.ResyncWithError(follow, "expected identifier");
							return null;
						}

						break;

					// Args
					case TokenKind.LeftCurly:
					case TokenKind.LeftRound:
					case TokenKind.NumericLiteral:
					case TokenKind.StringLiteral:
					case TokenKind.True:
					case TokenKind.False:
					case TokenKind.Nil:
						args = this.ParseArgs(follow | SuffixLookAhead);
                        Arg[] tempArray2 = new Arg[args.Count];
                        for (int i=0;i<args.Count;i++)
                            tempArray2[i] = args[i];
						result = new FunctionCall(GetSpan(), result, null, tempArray2);
						break;

					default:
						this.ResyncWithError(follow, "expected field lookup or function call");
						return null;
				}
			}

			return result;
		}

		// Arguments can be table constructors, primitive literals or optional
		// expression lists
		private Collections.IList<Arg> ParseArgs(TokenKind follow)
		{
            Collections.IList<Arg> args = new Collections.List<Arg>();
            Collections.IList<Expression> exprs;
            
            switch (this.tokens.Peek().Kind)
            {
				case TokenKind.LeftCurly:
					// table constructor
                    args = new Collections.List<Arg>();
                    Expression expr = this.ParseTableCtor(follow);
                    args.Add(Arg.Simple(expr));
                    return args;

                case TokenKind.LeftRound:
					// possibly empty expression list
					this.tokens.Read();

					if (this.tokens.Peek().Kind == TokenKind.RightRound)
					{
						exprs = new Collections.List<Expression>();
					}
					else
					{
						exprs = this.ParseExpList(follow);
					}

					if (this.tokens.Peek().Kind == TokenKind.RightRound)
					{
						this.tokens.Read();
                        foreach (Expression e in exprs)
                            args.Add(Arg.Simple(e));
						return args;
					}
					else
					{
						this.ResyncWithError(follow, "expected ')'");
						return null;
					}


                case TokenKind.NumericLiteral:
				case TokenKind.StringLiteral:
				case TokenKind.True:
				case TokenKind.False:
				case TokenKind.Nil:
					// primitive literal
					Token token = this.tokens.Read();
                    args.Add(Arg.Simple(new LiteralExpr(token.Span, token.Value)));
                    return args;

                default:
					this.ResyncWithError(follow, "expected args");
					return null;
			}
        }

		// Table constructor, a list of field declarations
		private TableCtor ParseTableCtor(TokenKind follow)
		{
			if (this.tokens.Peek().Kind == TokenKind.LeftCurly)
			{
                this.tokens.Read();
            }
			else
			{
				this.ResyncWithError(follow, "expected '{'");
				return null;
			}

			Collections.IList<FieldDecl> fields = new Collections.List<FieldDecl>();
			bool done = this.tokens.Peek().Kind == TokenKind.RightCurly;

			while (!done)
			{
				fields.Add(this.ParseFieldDecl(TokenKind.Semi | TokenKind.Comma | TokenKind.RightCurly));

				if ((this.tokens.Peek().Kind & (TokenKind.Semi | TokenKind.Comma)) == 0)
				{
					// no field separator, must be done parsing fields
					done = true;
				}
				else
				{
					// , or ; may be separator or optional trailing ,/;
					this.tokens.Read();
					done = this.tokens.Peek().Kind == TokenKind.RightCurly;
				}
			}

			if (this.tokens.Peek().Kind == TokenKind.RightCurly)
			{
				this.tokens.Read();
				return new TableCtor(GetSpan(), fields);
			}
			else
			{
				this.ResyncWithError(follow, "expected '}'");
				return null;
			}
		}

		private FieldDecl ParseFieldDecl(TokenKind follow)
		{
			if (this.tokens.Peek().Kind == TokenKind.LeftSquare)
			{
				Expression slotExpr = this.ParseExpr(TokenKind.RightSquare);
				
				if (this.tokens.Peek().Kind != TokenKind.RightSquare)
				{
					this.ResyncWithError(follow, "expected ']'");
					return null;
				}

				this.tokens.Read();

				if (this.tokens.Peek().Kind != TokenKind.Equals)
				{
					this.ResyncWithError(follow, "expected '='");
					return null;
				}

				this.tokens.Read();

				return new FieldDecl(GetSpan(), slotExpr, this.ParseExpr(follow));
			}
			else
			{
				// may be named field or expression

				Expression expr = this.ParseExpr(follow | TokenKind.Equals);

				if (expr is NamedVar && this.tokens.Peek().Kind == TokenKind.Equals)
				{
					// actually a named field

					Expression initExpr = this.ParseExpr(follow);
					return new FieldDecl(GetSpan(), new LiteralExpr(expr.Span, ((NamedVar)expr).Name), initExpr);
				}
				else
				{
					// an expression with assigned ordinal
					return new FieldDecl(expr == null ? GetSpan() : expr.Span, null, expr);
				}
			}
		}

/*
	The Lua grammar rules don't specify operator precedence (they are
	specified elsewhere.)

	Modified grammar including precedence and associativity:

	exp  ::= exp1 {OR exp1}

	exp1 ::= exp2 {AND exp2}

	exp2 ::= exp3 {< | > | <= | >= | ~= | ==  exp3}

	exp3 ::= exp4 [.. exp3]   *** right associative

	exp4 ::= exp5 {+ | -  exp4}

	exp5 ::= exp6 {* | /  exp5}
		
	exp6 ::= {NOT | -} exp7

	exp7 ::= exp8 [^ exp7]    *** right associative

	exp8 ::= literal | prefixexp | function | tableconstructor
 */
		private Expression ParseExpr(TokenKind follow)
		{
			Expression expr = this.ParseExp1(follow | TokenKind.Or);

			while (this.tokens.Peek().Kind == TokenKind.Or)
			{
				Expression right = this.ParseExp1(follow | TokenKind.Or);
				expr = new BinExpr(GetSpan(), expr, Operators.BitwiseOr, right);
			}

			return expr;
		}

		private Expression ParseExp1(TokenKind follow)
		{
			Expression expr = this.ParseExp2(follow | TokenKind.And);

			while (this.tokens.Peek().Kind == TokenKind.And)
			{
				Expression right = this.ParseExp2(follow | TokenKind.And);
				expr = new BinExpr(GetSpan(), expr, Operators.AndAlso, right);
			}

			return expr;
		}

		private Expression ParseExp2(TokenKind follow)
		{
			const TokenKind Exp2Ops =
				TokenKind.Less | TokenKind.Greater |
				TokenKind.LessEquals | TokenKind.GreaterEquals |
				TokenKind.TildeEquals | TokenKind.EqualsEquals;

			Expression expr = this.ParseExp3(follow | Exp2Ops);

			while ((this.tokens.Peek().Kind & Exp2Ops) != 0)
			{
				Token token = this.tokens.Read();
                Operators op;

				switch (token.Kind)
				{
					case TokenKind.Less:
						op = Operators.LessThan;
						break;

					case TokenKind.Greater:
						op = Operators.GreaterThan;
						break;

					case TokenKind.LessEquals:
						op = Operators.LessThanOrEqual;
						break;

					case TokenKind.GreaterEquals:
						op = Operators.GreaterThanOrEqual;
						break;

					case TokenKind.TildeEquals:
						op = Operators.NotEqual;
						break;

					case TokenKind.EqualsEquals:
						op = Operators.Equal;
						break;

					default:
						Diagnostics.Debug.Fail("unreachable");
						throw new System.Exception();
				}

				Expression right = this.ParseExp3(follow | Exp2Ops);
				expr = new BinExpr(GetSpan(), expr, op, right);
			}

			return expr;
		}

		private Expression ParseExp3(TokenKind follow)
		{
			Expression expr = this.ParseExp4(follow | TokenKind.DotDot);

			if (this.tokens.Peek().Kind == TokenKind.DotDot)
			{
                tokens.Read();
				return new BinExpr(GetSpan(), expr, Operators.ReverseAdd, this.ParseExp3(follow));
			}
			else
			{
				return expr;
			}
		}

		private Expression ParseExp4(TokenKind follow)
		{
			Expression expr = this.ParseExp5(follow | TokenKind.Plus | TokenKind.Minus);

			while ((this.tokens.Peek().Kind & (TokenKind.Plus | TokenKind.Minus)) != 0)
			{
				Token token = this.tokens.Read();
				Operators op = token.Kind == TokenKind.Plus ? Operators.Add : Operators.Subtract;
				Expression right = this.ParseExp5(follow | TokenKind.Plus | TokenKind.Minus);
				expr = new BinExpr(GetSpan(), expr, op, right);
			}

			return expr;
		}

		private Expression ParseExp5(TokenKind follow)
		{
			Expression expr = this.ParseExp6(follow | TokenKind.Star | TokenKind.Slash);

			while ((this.tokens.Peek().Kind & (TokenKind.Star | TokenKind.Slash)) != 0)
			{
				Token token = this.tokens.Read();
				Operators op = token.Kind == TokenKind.Star ? Operators.Multiply : Operators.Divide;
				Expression right = this.ParseExp6(follow | TokenKind.Star | TokenKind.Slash);
				expr = new BinExpr(GetSpan(), expr, op, right);
			}

			return expr;
		}

		private Expression ParseExp6(TokenKind follow)
		{
			if (this.tokens.Peek().Kind == TokenKind.Minus)
			{
                this.tokens.Read();
				return new UnExpr(GetSpan(), UnOp.UMinus, this.ParseExp6(follow));
			}
			else if (this.tokens.Peek().Kind == TokenKind.Not)
			{
                tokens.Read();
				return new UnExpr(GetSpan(), UnOp.Not, this.ParseExp6(follow));
			}
			else
			{
				return this.ParseExp7(follow);
			}
		}

		private Expression ParseExp7(TokenKind follow)
		{
			Expression expr = this.ParseExp8(follow | TokenKind.Caret);

			if (this.tokens.Peek().Kind == TokenKind.Caret)
			{
                tokens.Read();
				return new BinExpr(GetSpan(), expr, Operators.GetMemberNames, this.ParseExp7(follow));
			}
			else
			{
				return expr;
			}
		}

		private Expression ParseExp8(TokenKind follow)
		{
			switch (this.tokens.Peek().Kind)
			{
				case TokenKind.NumericLiteral:
				case TokenKind.StringLiteral:
				case TokenKind.True:
				case TokenKind.False:
				case TokenKind.Nil:
					Token token = this.tokens.Read();
					return new LiteralExpr(GetSpan(), token.Value);

				case TokenKind.Function:
					this.tokens.Read();
					return this.ParseFuncBody(follow);

				case TokenKind.LeftCurly:
					return this.ParseTableCtor(follow);

				default:
					return this.ParsePrefixExpr(follow);
			}
		}

		// Function body-- just a parameter list and chunk
		private AnonFunDecl ParseFuncBody(TokenKind follow)
		{
			if (this.tokens.Peek().Kind != TokenKind.LeftRound)
			{
				this.ResyncWithError(follow, "expected '('");
				return null;
			}

			Collections.List<ParamDecl> parameters = new Collections.List<ParamDecl>();
			bool varArgs = false;
			bool done = (this.tokens.Peek().Kind & (TokenKind.RightRound | TokenKind.EndOfFile)) != 0;

			while (!done)
			{
				if (this.tokens.Peek().Kind == TokenKind.Identifier)
				{
					Token token = this.tokens.Read();
					parameters.Add(new ParamDecl(GetSpan(), (string)token.Value));
				}
				else if (this.tokens.Peek().Kind == TokenKind.DotDotDot)
				{
					this.tokens.Read();
					varArgs = true;
					break; // done: ... last thing in specification
				}
				else
				{
					this.ResyncWithError(follow, "expected identifier");
					return null;
				}

				if (this.tokens.Peek().Kind == TokenKind.Comma)
				{
					this.tokens.Read();
				}
				else
				{
					done = true;
				}
			}

			if (this.tokens.Peek().Kind != TokenKind.RightRound)
			{
				this.ResyncWithError(follow, "expected ')'");
				return null;
			}

			this.tokens.Read();
			Statement body = this.ParseChunk(TokenKind.End);

			if (this.tokens.Peek().Kind != TokenKind.End)
			{
				this.ResyncWithError(follow, "expected 'end'");
				return null;
			}

			this.tokens.Read();
			return new AnonFunDecl(GetSpan(), parameters, varArgs, body);
		}
	}
}
